package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayDeque;

/*
111.二叉树的最小深度
 */
public class Of20210308LeetCode111 {
    /*
    给定一个二叉树，找出其最小深度。
    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    说明: 叶子节点是指没有子节点的节点。
     */
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1, null, new TreeNode(2, new TreeNode(4), new TreeNode(3, new TreeNode(6), new TreeNode(5))));
        System.out.println(minDepth2(node));
    }

    /*
    「最小深度是从根节点到最近叶子节点的最短路径上的节点数量。」，注意是「叶子节点」。
     */
    /*
    递归法 (有点问题)
     */
    private static int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right != null) {
            return 1 + minDepth(root.right);
        }
        if (root.left != null && root.right == null) {
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

    /*
    迭代法
     */
    private static int minDepth2(TreeNode root) {
        if (root == null) return 0;
        ArrayDeque<TreeNode> que = new ArrayDeque<>(10);
        int depth=0;
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            boolean flag = false;
            for (int i = 0; i < size; i++) {
                TreeNode node = que.remove();
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
                if (node.left == null && node.right == null) {
                    flag=true;
                    break;
                }
            }
            if (flag) break;
            depth++;
        }
        return depth;
    }
}
